package com.future.interview;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Description:面试题 16.20. T9键盘
 * 在老式手机上，用户通过数字键盘输入，手机将提供与这些数字相匹配的单词列表。每个数字映射到0至4个字母。给定一个数字序列，
 * 实现一个算法来返回匹配单词的列表。你会得到一张含有有效单词的列表。映射如下图所示：img/Solution_1620.png
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/t9-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * <p>
 * <img width="527" height="262" src="/Users/weiruibai.vendor/workspace/wrb/algorithm/leetcode/img/Solution_interview_1620.png" alt="">
 * <p>
 * 示例 1:
 * 输入: num = "8733", words = ["tree", "used"]
 * 输出: ["tree", "used"]
 * 示例 2:
 * 输入: num = "2", words = ["a", "b", "c", "d"]
 * 输出: ["a", "b", "c"]
 *
 * @author weiruibai.vendor
 * Date: 2022/12/20 09:11
 */
public class Solution_1620 {

    private static Solution_1620 INSTANCE = new Solution_1620();

    public static void main(String[] args) {
        String num = "8733";
        String[] words = {"tree", "used"};
        num = "2";
        words = new String[]{"a", "b", "c", "d"};

        num = "9675973753";
        words = new String[]{"alasvnpzur", "znwdgoiwso", "wduzrpnqrv", "ymrkxqdrlf", "epsqjclyqe", "zopjysdqke", "zhfxsdeimz", "eitgrsdnvt"};
        // ["ymrkxqdrlf","zopjysdqke"]
        List<String> validT9Words = INSTANCE.getValidT9Words(num, words);

    }


    public List<String> getValidT9Words(String num, String[] words) {
        if (num == null || "".equals(num) || words == null || words.length == 0) {
            return new ArrayList<>();
        }
        Map<Character, List<String>> characterMap = buildCharacterMap();
        char[] chars = num.toCharArray();
        int index = 0;
        /**
         * 为了方便，转成list，方便进行add remove操作
         * 不要用Arrays.asList(words)，这样转出来的数组不能进行add remove等操作！！
         */
        List<String> targets = new ArrayList<>();// Arrays.asList(words);
        for (String st : words) {
            targets.add(st);
        }
        for (char ch : chars) {
            List<String> list = characterMap.get(ch);
            List<String> newArr = new ArrayList<>();
            for (int i = 0; i < targets.size(); i++) {
                String str = targets.get(i);
                char c = str.charAt(index);
                if (list.contains(String.valueOf(c))) {
                    /**
                     * 符合就添加到新数组中，不要在原来数组targets上进行remove!!
                     */
                    newArr.add(str);
                }
            }
            index++;
            /**
             * 把新的数组赋值到targets
             */
            targets = newArr;
        }
        return targets;
    }

    private Map<Character, List<String>> buildCharacterMap() {
        Map<Character, List<String>> map = new HashMap<>();
        map.put('2', Arrays.asList("abc".split("")));
        map.put('3', Arrays.asList("def".split("")));
        map.put('4', Arrays.asList("ghi".split("")));
        map.put('5', Arrays.asList("jkl".split("")));
        map.put('6', Arrays.asList("mno".split("")));
        map.put('7', Arrays.asList("pqrs".split("")));
        map.put('8', Arrays.asList("tuv".split("")));
        map.put('9', Arrays.asList("wxyz".split("")));
        return map;
    }


}
